package org.example.myleet.p740;

import java.util.*;

/**
 * 26 ms
 * 动态规划，dp[i] = Max(dp[j] + numList[i] * freq[i])
 */
public class Solution {
    public int deleteAndEarn(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //计算每个数字的出现次数，并去重
        HashMap<Integer, Integer> numFreq = new HashMap<>();
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            int freq = numFreq.getOrDefault(num, 0);
            numFreq.put(num, ++freq);
            numSet.add(num);
        }
        List<Integer> numList = new ArrayList<>(numSet);
        //升序排列
        numList.sort(Comparator.naturalOrder());
        int reply = 0;
        //dp[i]代表删除numList中第i个数字可以得到的最高点数
        int[] dp = new int[numList.size()];
        //初始化0和1位的情况
        dp[0] = numList.get(0) * numFreq.getOrDefault(numList.get(0), 0);
        reply = Math.max(reply, dp[0]);
        dp[1] = numList.get(1) * numFreq.getOrDefault(numList.get(1), 0);
        if (numList.get(1) > numList.get(0) + 1) {
            dp[1] = dp[0] + dp[1];
        }
        reply = Math.max(reply, dp[1]);
        for (int i = 2; i < numList.size(); ++i) {
            //删除当前数字的所能得到的点数
            int t = numList.get(i) * numFreq.getOrDefault(numList.get(i), 0);
            for (int j = i - 1; j >= 0; --j) {
                //往前搜寻，寻找最大的dp[j] + t，作为dp[i]
                if (numList.get(i) - numList.get(j) > 1) {
                    dp[i] = Math.max(dp[i], dp[j] + t);
                }
            }
            //刷新最大的点数的答案
            reply = Math.max(reply, dp[i]);
        }
        return reply;
    }
}
